package com.sunny.l117;

/**
 * @Author zsunny
 * @Date 2018/9/20 9:33
 * @Mail zsunny@yeah.net
 */
public class Solution {
    public int search(int[] A, int target) {
        if(null == A){
            return -1;
        }
        int len = A.length;
        if(1 == len){
            if(target == A[0]){
                return 0;
            }else{
                return -1;
            }
        }
        if(A[0] < A[len-1]){
            return binarySearch(A, 0, len-1, target);
        }else{
            int mind = bsearch(A, 0, len-1);
            if(target >= A[0]){
                return binarySearch(A, 0, mind-1, target);
            }else if(target <= A[len-1]){
                return binarySearch(A, mind, len-1, target);
            }else{
                return -1;
            }
        }
    }

    public int bsearch(int[] arr, int s, int t){
        while (s < t){
            int mid = (s+t)>>1;
            if(arr[mid] > arr[t]){
                s = mid+1;
            }if(arr[mid] < arr[t]){
                t = mid;
            }
        }
        return s;
    }

    public int binarySearch(int[] arr, int s, int t, int target){
        if(arr[s] > target || arr[t] < target){
            return -1;
        }
        while (s <= t){
            int mid = (s+t)>>1;
            if(arr[mid] > target){
                t = mid - 1;
            }else if(arr[mid] < target){
                s = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}
